package com.dlut.java;


import java.util.Random;
import java.util.Scanner;

/**
 * n座城市，m天任务，收益为a或者b
 */
public class T1_MaxProfit {
    public static void main(String[] args) {
/*
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        int[] c = new int[m];
        int[] a = new int[m];
        int[] b = new int[m];
        for (int i = 0; i < m; i++) {
            c[i] = in.nextInt();
        }
        for (int i = 0; i < m; i++) {
            a[i] = in.nextInt();
        }
        for (int i = 0; i < m; i++) {
            b[i] = in.nextInt();
        }
*/
        for (int i = 0; i < 100000; i++) {
            boolean b = test();
            if (!b){
                System.out.println("出错了");
            }
//            System.out.println(r.nextInt(10));
        }
        System.out.println("成功了");


//        int ans = fun(c, a, b, k, 0, m);
//        int ans2 = fun2(c, a, b, k, n, m);
//        System.out.println(ans == ans2);
    }


    static Random r = new Random();
    public static boolean test(){

        int m = r.nextInt(20) + 1;
        int k = r.nextInt(20) + 1;
        int n = r.nextInt(20) + k;

        int[] c = new int[m];
        int[] a = new int[m];
        int[] b = new int[m];
        for (int i = 0; i <m; i++) {
            c[i] = r.nextInt(n) + 1;
            a[i] = r.nextInt(1000);
            b[i] = r.nextInt(1000);
        }

        int ans = fun(c, a, b, k, 0, m);
        int ans2 = fun2(c, a, b, k, n, m);
        if (ans != ans2){
            System.out.println("出错了");
        }
        return ans == ans2;
    }

    /**
     * 动态规划解法
     * @param c 任务所在城市
     * @param a 在这个城市的任务奖励
     * @param b 不在这个城市的任务奖励
     * @param k 初始城市
     * @param n 城市的数量
     * @param m 任务的天数
     * @return 任务奖励的最大值
     */
    public static int fun2(int[] c,int[] a, int[] b, int k,int n, int m){
        int[][] pro = new int[n + 1][m];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                pro[i][j] = -1;
            }
        }
        if (k == c[0])
            pro[k][0] = a[0];
        else {
            pro[k][0] = 0;
            pro[c[0]][0] = b[0];
        }
        for (int i = 1; i < m; i++) {
            int temp = -1;
            for (int j = 1; j <= n; j++) {
                pro[j][i] = pro[j][i - 1];
                if (pro[j][i] != -1 && j != c[i]) {
                    temp = Math.max(temp, pro[j][i]);
                }
            }
            if (pro[c[i]][i] != -1) {
                if (temp == -1)
                    pro[c[i]][i] += a[i];
                else
                    pro[c[i]][i] = Math.max(a[i] + pro[c[i]][i], b[i] + temp);
            } else {
                pro[c[i]][i] = b[i] + temp;
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, pro[i][m - 1]);
        }
        return ans;
    }


//        int ans = fun(c, a, b, k, 0, m);
//        System.out.println(ans);
    /**
     * 递归解法
     * @param c 任务所在城市
     * @param a 在这个城市的任务奖励
     * @param b 不在这个城市的任务奖励
     * @param k 初始城市
     * @param i 任务执行到第i天
     * @param m 任务的天数
     * @return 任务奖励的最大值
     */
    public static int fun(int[] c,int[] a, int[] b, int k, int i, int m){
        if (i == m-1){
            if (k == c[i])
                return a[i];
            else
                return b[i];
        }
        int ans = 0;
        if (k == c[i]){
            ans = a[i] + fun(c, a, b, k, i + 1, m);
        }else{
            int temp1 = b[i] + fun(c, a, b, c[i], i + 1, m);
            int temp2 = fun(c, a, b, k, i + 1, m);
            ans = Math.max(temp1, temp2);
        }
        return ans;
    }
}
